1. Field
The present invention generally relates to communication and, in particular, to hybrid automatic request (H-ARQ) rate compatible coding for high throughput applications.
2. Background
Generally, in the case of data transmission, a receiver observes each received bit in the presence of noise or distortion and only an indication of the bit's value is obtained. Under these circumstances one interprets the observed values as a source of “soft” bits. A soft bit indicates a preferred estimate of the bit's value, i.e., a one or a zero, together with some indication of that estimate's reliability. While the number of errors may be relatively low, even a small number of errors or level of distortion can result in the data being unusable or, in the case of transmission errors, may necessitate re-transmission of the data.
In order to provide a means to check for errors and, in some cases, to correct errors, binary data can be coded to introduce carefully designed redundancy. Coding of a unit of data produces what is commonly referred to as a codeword. Because of its redundancy, a codeword will often include more bits than the input unit of data from which the codeword was generated.
When signals arising from transmitted codewords are received or processed, the redundant information included in the codeword as observed in the signal can be used to identify and/or correct errors in or remove distortion from the received signal in order to recover the original data unit. Such error checking and/or correcting can be implemented as part of a decoding process. In the absence of errors, or in the case of correctable errors or distortion, decoding can be used to recover from the source data being processed, the original data unit that was encoded. In the case of unrecoverable errors, the decoding process may produce some indication that the original data cannot be fully recovered. These decoding failure indications of decoding failure can be used to initiate retransmission of the data.
Communication systems often need to operate at several different rates. One way to keep the implementation as simple as possible and to provide for the coding and decoding at the different rates is to use low-density-parity check (LDPC) codes. In particular, the LDPC codes are used to generate higher-rate codes by puncturing lower-rate codes. With communication systems that employ rate adaptation, the transmission data rate may need to be adjusted according to the conditions and demands of the system. Rate adaption allows a communication system, and the components thereof, to flexibly and efficiently adapt the data rate to the current channel conditions. Typical error correcting designs, for example, select a fixed code, the code having a certain rate and correction capability. To add flexibility for handling different amounts of data having different error protection requirements, the rate is adapted to time-varying channel conditions, as well as compensating for insufficiently known parameters.
For flexible channel encoding, the data bits may be grouped into blocks of varying size, and these blocks may be encoded with different amounts of redundancy. Instead of using several separate error correcting codes to encode the different groups of bits, it is desirable to use a single parent code that may accommodate several rates. This is referred to as rate-compatible coding. With the rapid development of mobile communication systems, there remains a need in the art for rate-compatible LDPC codes suitable for hybrid ARQ applications with high throughput.
LDPC methods can recover codewords in very noisy environments. Two examples of communication channel models are the binary erasure channel (BEC) and the binary symmetric channel (BSC). These channels are illustrated in FIGS. 1A and 1B. The input is binary in that it is comprised of bits having the value 0 or 1.
With respect to outputs, the BEC has an output of 0, 1 or erasure. The probability that a bit was transferred correctly is 1−p, and the probability that a bit was erroneously transferred, i.e., erased, is p. With BSC, the output is 0 or 1. The probability that a bit was transferred correctly is 1−p, and the probability that a bit was erroneously transferred, i.e., a zero was received when a one was sent and vica versa, is p.
LDPC codes are linear codes which are generated from sparse bipartite graphs. A bipartite graph, also called a bigraph, is a set of graph vertices decomposed into two disjoint sets such that no two graph vertices within the same set are adjacent. A bipartite graph is a special case of a k-partite graph with k=2. If there are p and g graph vertices in the two sets, the complete bipartite graph is denoted Kp,q. By sparse we mean that the LDPC code is a special class of linear block codes whose parity check matrix H has a low density of ones. This sparsity renders low complexity decoding leads to simple implementation. FIG. 2 is an example of such a graph. The graph contains V variable nodes, vi on the left and C check nodes, cj on the right. The V variable nodes may also be called message or systematic nodes.
The bipartite graph may be represented by a simplified adjacency matrix. H with C rows and V columns. See FIG. 3. FIG. 3 is an example of a binary sparse C×V parity check matrix H. If a j-th check node is connected to an i-th variable node by an edge, i.e., the two nodes are neighbors, then there is a one in the i-th column and in the j-th row of a parity check matrix H. That is, the intersection of an-i-th row and a j-th column contains a “1” where an edge joins the corresponding vertice and a “0” where there is no edge. A variable node and a constraint (or check) node are said to be neighbors if they are connected by an edge in the graph. Edges, E, in the graph connect variable nodes to constraint or check nodes and each edge corresponds to a non-zero entry in the parity check matrix. Each row of matrix H corresponds to a check node and represents a parity check and each column corresponds to one of the variable nodes and represents a demodulated symbol. Since there are 5 variable nodes and 3 check nodes, the matrix includes 5 columns and 3 rows.
The number of demodulated symbols or variable nodes N is the LDPC code length. The number of non-zero elements in a row (column) is defined as the row (column) weight dc(dv). A regular graph or code is one for which all variable nodes have the same degree, j say, and all constraint nodes have the same degree, k say. In this case we say that the code is a (j,k) regular code. On the other hand, an irregular code has constraint nodes and/or variable nodes of differing degrees. For example, some variable nodes may be of degree 4, others of degree 3 and still others of degree 2.
To each variable node is associated one bit of the codeword. A bit sequence associated one-to-one with the variable node sequence is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones. In some cases some of these bits might be punctured or known, as discussed further below. Puncturing is the act of removing bits from a codeword to yield, in effect, a shorter codeword. In the case of LDPC graphs this means that some of the variable nodes in the graph correspond to bits that are not actually transmitted.
The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages within the graph along the edges and updating these messages by performing computations at the nodes based on the incoming messages. Such methods will be generally referred to as message passing methods. Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. Ideally, the estimates for separate bits are statistically independent. This ideal may be violated in practice. A received word is comprised of a collection of received values.
The degree of a node refers to the number of edges connected to that node. This feature is illustrated in the H matrix shown in FIG. 3 where the number of edges incident to vi is equal to the number of ones in column i and is called the variable node degree d(vi). Similarly, the number of edges connected with cj is equal to the number of ones in row j and is called the check node degree d(cj).
In hybrid ARQ applications, all the data symbols are transmitted during the first transmission with a high rate code. If the packet was not successfully decoded, the transmitter would send more redundancy symbols to increase the reliability of the already transmitted packet. These redundancy symbols when combined with the previously received packet make another codeword of a relatively lower rate since information bits are punctured by the added redundancy symbols. The transmitter will incrementally send redundancy symbols, thus decreasing the overall rate of the transmitted packet until the receiver acknowledges the successful decoding of the packet. Rate-compatible structured LDPC codes in the prior art may have the undesired property that the information block size at the protograph level is not constant which may make them unsuitable for H-ARQ applications. In addition, in the prior art, low-rate structured LDPC codes may have the undesired property that the punctured variable nodes have very high degrees. Therefore, it may be difficult to puncture them to achieve high rates.